#pragma once
#include<iostream>
#include<vector>
#include<string>

template<class T>
struct HashFunc {
	int operator()(const T& key)
	{
		return (size_t)key;
	}
};
template <>
struct HashFunc<std::string> {
	int operator()(const std::string& key)
	{
		int _num = 0;
		for (auto& e : key)
		{
			_num *= 131;
			_num += e;
		}
		return _num;
	}
};

namespace MyHashBucket {
	template <class T>
	struct hashNode {

		//pair<K, V> _data;
		T _data;
		hashNode* _next;

		hashNode(T data)
			:_data(data),_next(nullptr)
		{ }

	};

	using namespace std;

	template <class T, class KOfT, class Hash = HashFunc<T>>
	class hashTable {
		typedef hashNode<T> Node;
	public:

		hashTable():_size(0)
		{
			_table.resize(10, nullptr);
		}
		Node* Find(const T& data)
		{
			Hash hs;
			KOfT kot;
			int hashi = hs(kot(data)) % _table.size();
			Node* cur = _table[hashi];
			while (cur)
			{
				if (kot(cur->_data) == kot(data))
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;

		}
		bool Insert(const T& data )
		{
			if (Find(data) != nullptr)
			{
				return false;
			}
			Hash hs;
			KOfT kot;
			if (_size == _table.size())
			{

				vector<Node*> _newtable(_table.size() * 2, nullptr);
				for (auto& e : _table)
				{
					if (e != nullptr)
					{
						Node* cur = e;
						while (cur)
						{
							Node* next = cur->_next;

							int hashi = hs(kot(cur->_data)) % _newtable.size();

							if (_newtable[hashi] == nullptr)
							{
								_newtable[hashi] = cur;
								cur->_next = nullptr;
							}
							else
							{
								cur->_next = _newtable[hashi];
								_newtable[hashi] = cur;
							}
							cur = next;
						}
						e = nullptr;
					}
				}

				_table.swap(_newtable);
			}
			Node* newnode = new Node(data);
			int hashi = hs(kot(data)) % _table.size();

			if (_table[hashi] == nullptr)
			{
				_table[hashi] = newnode;
			}
			else
			{
				newnode->_next = _table[hashi];
				_table[hashi] = newnode;
			}
			_size++;
			return true;

		}

		bool Erase(const T& data)
		{
			Hash hs;
			KOfT kot;
			int hashi = hs(kot(data)) % _table.size();
			Node* cur = _table[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (kot(cur->_data) == kot(data))
				{
					if (prev == nullptr)
					{
						_table[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					_size--;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}
		void Print()
		{
			for (auto& e : _table)
			{
				if (e != nullptr)
				{
					Node* cur = e;
					while (cur)
					{
						cout << cur->_data.first << ":"  << cur->_data.second << endl;
						cur = cur->_next;
					}
				}
			}
			cout << endl;
		}

		int Size()
		{
			return _size;
		}
		~hashTable()
		{
			for (auto& e : _table)
			{
				if(e != nullptr)
				{
					Node* cur = e;
					Node* next;

					while (cur)
					{
						next = cur->_next;
						delete cur;
						cur = next;
					}
				}
				e = nullptr;
			}
		}
	private:
		vector<Node*> _table;
		size_t _size;

	};

	template<class K,class V>
	struct KOfT {
		const K& operator()(const pair<K,V>& data)
		{
			return data.first;
		}
	};
	void test1()
	{
		hashTable<pair<string,int>, KOfT<string,int>, HashFunc<string>> t;
		
		vector<string> ve = { "aaa","bbb","cc","aaa","aaa"};
		for (auto& e : ve)
		{
			t.Insert({ e,0 });
		}
		t.Print();

	}
}


namespace MyHashOpenAddr
{
	enum state {
		EXIT,
		OCCUPY,
		NIL
	};
	template <class T>
	struct hashNode {

		//pair<K, V> _data;
		T _data;
		state _st;
		hashNode(T data = T())
			:_data(data),_st(NIL)
		{
		}

	};

	using namespace std;

	template <class T, class KOfT, class Hash = HashFunc<T>>
	class hashTable {
		typedef hashNode<T> Node;
	public:

		hashTable() :_size(0)
		{
			_table.resize(10);
		}
		Node* Find(const T& data)
		{
			Hash hs;
			KOfT kot;
			int hashi = hs(kot(data)) % _table.size();
			while (_table[hashi]._st != NIL)
			{
				if (kot(_table[hashi]._data) == kot(data))
				{
					return &_table[hashi];
				}
				hashi++;
				hashi %= _table.size();
			}
			return nullptr;
		}
		bool Insert(const T& data)
		{
			if (Find(data) != nullptr)
			{
				return false;
			}
			Hash hs;
			KOfT kot;
			if ((_size * 10) / _table.size() >= 7)
			{

				vector<Node> _newtable(_table.size() * 2);
				for (auto& e : _table)
				{
					if (e._st != NIL )
					{
						int hashi = hs(kot(data)) % _table.size();

						while (_table[hashi]._st == OCCUPY)
						{
							hashi++;
							hashi %= _table.size();
						}

						_table[hashi] = e;
					}
				}

				_table.swap(_newtable);
			}
			Node* newnode = new Node(data);
			newnode->_st = OCCUPY;
			int hashi = hs(kot(data)) % _table.size();

			while (_table[hashi]._st == OCCUPY)
			{
				hashi++;
				hashi %= _table.size();
			}
		
			_table[hashi] = *newnode;
			_size++;
			return true;

		}

		bool Erase(const T& data)
		{
			Node* ptr = Find(data);
			if(ptr == nullptr)
			return false;

			ptr->_st = EXIT;
			return true;
		}
		void Print()
		{
			for (auto& e : _table)
			{
				if (e._st == OCCUPY)
				{
					cout << e._data.first<< " " << e._data.second << endl;
				}
			}
			cout << endl;
		}

		int Size()
		{
			return _size;
		}
		
		
	private:
		vector<Node> _table;
		size_t _size;

	};

	template<class K, class V>
	struct KOfT {
		const K& operator()(const pair<K, V>& data)
		{
			return data.first;
		}
	};
	void test1()
	{
		hashTable<pair<string, string>, KOfT<string, string>, HashFunc<string>> t;

		vector<string> ve = { "aaa","bbb","cc","s","fasd","kkk"};
		for (auto& e : ve)
		{
			 t.Insert({ e,e });
		}

	  //	t.Erase({"bbb","bbb"});

		t.Print();
	}
}